import java.util.Deque;
import java.util.LinkedList;

/**
 * @author LKQ
 * @date 2021/12/26 21:23
 * @description 方法一计算链表长度，方法二使用栈，方法三使用快慢指针，先让fast走n步，然后slow和fast一次一步。当fast指向null
 * 也即找到了要删除节点的前一个节点。
 */
public class FormalSolution {
    public static void main(String[] args) {

    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode temp = head;
        ListNode dummy = new ListNode(0, head);
        // 记录链表长度
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        ListNode cur = dummy;
        // 移动length - n次
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return dummy.next;
    }

    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        return dummy.next;
    }

    public ListNode removeNthFromEnd3(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }


}
